package com.wuhongyu.tree;

/**
 * 自平衡二叉搜索树
 */
public class AVLTree<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left;
        public Node right;
        public int height;

        public Node(E e){
            this.e = e;
            left= null;
            right = null;
            //空节点的高度是-1
            height = 0;
        }
    }


    //允许的左右孩子高度的最大差值
    private static final int ALLOW_HEIGHT = 1;
    private Node root;
    private int size;

    public AVLTree(){
        root = null;
        size = 0;
    }

    private int height(Node node){
        return node == null ? -1 : node.height;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }

    public void add(E e){
        root = add(root,e);
    }


    private Node add(Node node , E e){
        if(node == null){
            return new Node(e);
        }

        //e比当前的节点小,去左孩子找
        if(node.e.compareTo(e)>0){
            node.left =  add(node.left,e);
        }
        //e比当前的节点大,去右孩子找
        else if(node.e.compareTo(e)<0){
            node.right = add(node.right,e);
        }
        //进行旋转
        return balance(node);
    }

    /**
     * 二分搜索树的中序遍历,输出有序序列
     */
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node){
        if(node == null){
            return ;
        }

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    private Node balance(Node node) {
        if(node == null){
            return node;
        }
        //如果左孩子的高度比右孩子的高度高2,就进行旋转
        if(height(node.left) - height(node.right) > ALLOW_HEIGHT){
            //如果左孩子的左孩子比左孩子的右孩子高,就进行左单旋转...有点绕口
            if(height(node.left.left) >= height(node.left.right)){
                node = rotateWithLeft(node);
            }else {//否则进行左双旋转
                node = doubleWithLeft(node);
            }
        }else if(height(node.right) - height(node.left) > ALLOW_HEIGHT){
            if(height(node.right.right) >= height(node.right.left)){
                node = rotateWithRight(node);
            }else {
                node = doubleWithRight(node);
            }
        }
        node.height = Math.max(height(node.left),height(node.right))+1;
        return node;
    }

    //右双旋转
    private Node doubleWithRight(Node node) {
        //先对node的右孩子进行一次左旋转
        node.right = rotateWithLeft(node.right);
        //此时整个节点满足右旋转的条件了,直接进行右旋转
        return rotateWithRight(node);
    }


    //左双旋转
    private Node doubleWithLeft(Node node) {
        //先对node的左孩子进行一次右旋转
        node.left = rotateWithRight(node.left);
        //此时整个节点满足左旋转的条件了,直接进行左旋转
        return rotateWithLeft(node);
    }

    //右单旋转
    private Node rotateWithRight(Node node) {
        Node right = node.right;
        node.right = right.left;
        right.left = node;
        //给旋转后的高度重新赋值
        node.height = Math.max(height(node.left),height(node.right))+1;
        //两种写法,都是一个意思,被注释起来的比较好理解,没被注释的更帅气!!!哈哈
        //right.height = Math.max(height(right.right),height(right.left))+1;
        right.height = Math.max(height(right.right),node.height)+1;
        return right;
    }
    //左单旋转
    private Node rotateWithLeft(Node node) {
        Node left = node.left;
        node.left = left.right;
        left.right = node;
        //给旋转后的高度重新赋值
        node.height = Math.max(height(node.left),height(node.right))+1;
        //两种写法,都是一个意思,被注释起来的比较好理解,没被注释的更帅气!!!哈哈
        //left.height = Math.max(height(left.left),height(left.rigt))+1;
        left.height = Math.max(height(left.left),node.height)+1;
        return left;
    }


}